package travellersalesman;

import java.io.InputStream;
import java.util.Locale;
import java.util.Scanner;


public class RealExtendetGraph extends ExtendetGraph{
	private Point coord[];
	public RealExtendetGraph(InputStream in) {
		Scanner sc = new Scanner(in);
		sc.useLocale(Locale.US);
		vertexCount = sc.nextInt();
		initMatrix(vertexCount);
		coord = new Point[vertexCount];
		for(int i=0;i<vertexCount;++i) {
			int num = sc.nextInt()-1;
			double x = sc.nextDouble();
			double y = sc.nextDouble();
			coord[num] = new Point();
			coord[num].x = x;
			coord[num].y = y;
			
		}
		
		for(int i=0;i<vertexCount;++i) {
			for(int j = i;j<vertexCount;++j) {
				double distance = Math.sqrt(Math.pow(coord[j].x-coord[i].x, 2) + Math.pow(coord[j].y-coord[i].y, 2));
				matrix[i][j] = INF;
				matrix[j][i] = INF;
			}
		}
		
		while(true) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			if(i==-1)
				break;
			--i;--j;
			double distance = Math.sqrt(Math.pow(coord[j].x-coord[i].x, 2) + Math.pow(coord[j].y-coord[i].y, 2));
			matrix[i][j] = distance;
			matrix[j][i] = distance;
		}
		
		
		floydMatrix = new int[vertexCount][];
		distanceMatrix = new double[vertexCount][];
		
		for(int i = 0; i < vertexCount;++i) {
			floydMatrix[i] = new int[vertexCount];
			distanceMatrix[i] = new double[vertexCount];
			for (int j = 0; j < vertexCount; j++) {
				distanceMatrix[i][j] = matrix[i][j];
				if(matrix[i][j] < ExtendetGraph.INF) {
					floydMatrix[i][j] = i;
				}
				else {
					floydMatrix[i][j] = -1;
				}				
			}
		}
		
		for(int k=0 ;k<vertexCount;++k ) {
			for(int i=0; i<vertexCount; ++i) {
				for(int j=0; j<vertexCount; ++j) {
					if(distanceMatrix[i][j] > distanceMatrix[i][k] + distanceMatrix[k][j]) {
						distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j];
						floydMatrix[i][j] = floydMatrix[k][j];
					}
				}
			}
		}
	}
	public Point getPoint(int p) {
		return coord[p];
	}
	class Point {
		public double x;
		public double y;
		
		public Point() {
			x=0;
			y=0;
		}
	}
}
